#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define XH(i,a,b) for(int i = a; i < b; ++i)
#define XXH(i,b,a) for(int i = b; i >= a; --i)
#define Module 998244353
int tmpInt;ll tmpll;string tmpStr;char tmpChar;
vector<int>tmpIntVector;

int matrix[210][210] = {0};
int minDist[210][210] = {0};

int main(){
  int n,m;cin>>n>>m;
  XH(i,0,m){
    int s1,s2,dist;
    scanf("%d%d%d", &s1,&s2,&dist);
    matrix[s1][s2] = dist;
    matrix[s2][s1] = dist;
  }
  for(int i = 0; i <= n; ++i){
    int start = i;
    int dist[n+1],visit[n+1];
    fill(dist,dist+n+1,INT_MAX);
    fill(visit,visit+n+1,0);
    XH(j,0,n+1){
      if(matrix[start][j])dist[j] = matrix[start][j];
    }
    visit[start] = 1;
    while(1){
      int min = INT_MAX,choose = -1;
      XH(j,0,n+1){
        if(visit[j]==0 && dist[j]<min){
          min = dist[j];
          choose = j;
        }
      }
      if(choose == -1)break;
      visit[choose] = 1;
      for(int j = 0; j < n + 1; ++j){
        if(matrix[choose][j] && dist[choose] + matrix[choose][j] < dist[j] && visit[j] == 0){
          dist[j] = dist[choose] + matrix[choose][j];
        }
      }
    }
    XH(j,0,n+1)minDist[start][j] = dist[j];
  }
  
  int now = 0;
  int visit[n+1];
  int sum = 0;
  vector<int>path;
  path.push_back(0);
  fill(visit,visit+n+1,0);
  visit[0] = 1;
  while(1){
    int min = INT_MAX, choose = -1;
    for(int i = 0; i<n+1; ++i){
      if(visit[i] == 0 && minDist[now][i] < min){
        min = minDist[now][i];
        choose = i;
      }
    }
    if(choose == -1)break;
    visit[choose] = 1;
    path.push_back(choose);
    sum += min;
    now = choose;
  }
  XH(i,0,path.size()){
    printf("%d%c",path[i],i==path.size()-1?'\n':' ');
  }
  if(path.size()<n+1){
    int less = n + 1 - path.size();
    XH(i,0,n+1){
      if(visit[i] == 0){
        printf("%d",i);
        less--;
        if(less>0)printf(" ");
        else printf("\n");
      }
    }
  }else{
    printf("%d\n",sum);
  }

  return 0;
}
